package com.c2b.algorithm.leetcode.base;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href="https://leetcode.cn/problems/kth-smallest-element-in-a-bst/"> 二叉搜索树中第K小的元素(Kth Smallest Element in a BST)</a>
 * <p>给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [3,1,4,null,2], k = 1
 *      输出：1
 *
 * 示例 2：
 *      输入：root = [5,3,6,2,4,null,null,1], k = 3
 *      输出：3
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中的节点数为 n 。</li>
 *     <li>1 <= k <= n <= 10^4</li>
 *     <li>0 <= Node.val <= 10^4</li>
 * </ul>
 * </p>
 *
 * <b>进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？</b>
 * ==> 将二叉搜索树转换为平衡二叉搜索树，可以参考<a href="将二叉搜索树转换为平衡二叉搜索树，可以参考「1382. 将二叉搜索树变平衡的官方题解」">「1382. 将二叉搜索树变平衡的官方题解」</a>
 *
 * @author c2b
 * @since 2023/10/19 9:43
 */
public class LC0230KthSmallestElementInBST {

    static class Solution {
        public int kthSmallest(TreeNode root, int k) {
            // 中序遍历
            Deque<TreeNode> stack = new LinkedList<>();
            TreeNode currNode = root;
            while (!stack.isEmpty() || currNode != null) {
                // 将以当前节点为根节点的树中，所有左子节点入栈
                while (currNode != null) {
                    stack.push(currNode);
                    currNode = currNode.left;
                }
                currNode = stack.pop();
                --k;
                if (k == 0) {
                    return currNode.val;
                }
                currNode = currNode.right;
            }
            return -1;
        }
    }


    public static void main(String[] args) {
        Solution solution = new Solution();

        TreeNode node1 = new TreeNode(3);
        node1.left = new TreeNode(1);
        node1.left.right = new TreeNode(2);
        node1.right = new TreeNode(4);
        System.out.println(solution.kthSmallest(node1, 1));

        TreeNode node2 = new TreeNode(5);
        node2.left = new TreeNode(3);
        node2.right = new TreeNode(6);
        node2.left.left = new TreeNode(2);
        node2.left.left.left = new TreeNode(1);
        node2.left.right = new TreeNode(4);
        System.out.println(solution.kthSmallest(node2, 3));
    }
}
